/*
 * Copyright (c) 2010-2013 Ruben Chakhmakhchyan. All rights reserved.
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Eclipse Public License
 * Version 1.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://opensource.org/licenses/EPL-1.0 and read it before using this file.
 */

#pragma once

#include <stdlib.h>
#include <string.h>


template<class A>
class ListConstIterator
{
public:

    typedef typename A::ConstReference Reference;
    typedef typename A::Pointer Pointer;
    typedef ListConstIterator<typename A> Type;

public:

    ListConstIterator() : m_ptr( 0 ) { }

    ListConstIterator( Pointer p )
    {
        m_ptr = p;
    }

    Reference operator * () const
    {
        return ( *this->m_ptr );
    }

    Pointer operator -> () const
    {
        return ( &**this );
    }

    Type& operator ++ ()
    {
        ++*( Type* ) this;
        return *this;
    }

    Type operator ++ ( int )
    {
        Type tmp = *this;
        ++*this;
        return tmp;
    }

    Type& operator -- ()
    {
        --*( Type* ) this;
        return *this;
    }

    Type operator -- (int)
    {
        Type tmp = *this;
        --*this;
        return tmp;
    }

    Type& operator += ( size_t value )
    {
        *( Type* ) this += value;
        return *this;
    }

    Type operator + ( size_t value ) const
    {
        Type tmp = *this;
        return ( tmp += value );
    }

    Type& operator -= ( size_t value )
    {
        Type tmp = *this;
        return ( tmp -= value );
    }

    Type operator - ( size_t value ) const
    {
        Type tmp = *this;
        return tmp -= value;
    }

    int operator - ( const Type& right ) const
    {
        return ( m_ptr - right.m_ptr );
    }

    Reference operator [] ( int offset ) const
    {
        return *( *this + offset );
    }

    bool operator < ( const Type& right ) const
    {
        return ( this->m_ptr < right.m_ptr );
    }

    bool operator > ( const Type& right ) const
    {
        return ( right < *this );
    }

    bool operator <= ( const Type& right ) const
    {
        return ( !( right < *this ) );
    }

    bool operator >= ( const Type& right ) const
    {
        return ( !( *this < right ) );
    }

    bool operator == ( const Type& right ) const
    {
        return m_ptr == right.m_ptr;
    }

    bool operator != ( const Type& right ) const
    {
        return m_ptr != right.m_ptr;
    }

protected:

    Pointer m_ptr;
};

template<class A>
class ListIterator: public ListConstIterator<A>
{
public:

    typedef typename A::Reference Reference;
    typedef typename A::Pointer Pointer;
    typedef ListConstIterator<A> BaseType;
    typedef ListIterator<A> Type;

public:

    ListIterator() : m_ptr( 0 ) { }

    ListIterator( Pointer p )
        : BaseType( p )
    {
    }

    Reference operator * () const
    {
        return ( *this->m_ptr );
    }

    Pointer operator -> () const
    {
        return ( &**this );
    }

    Type& operator ++ ()
    {
        ++m_ptr;
        return *this;
    }

    Type operator ++ ( int )
    {
        Type tmp = *this;
        ++*this;
        return tmp;
    }

    Type& operator -- ()
    {
        --*( Type* ) this;
        return *this;
    }

    Type operator -- (int)
    {
        Type tmp = *this;
        --*this;
        return tmp;
    }

    Type& operator += ( size_t value )
    {
        *( Type* ) this += value;
        return *this;
    }

    Type operator + ( size_t value ) const
    {
        Type tmp = *this;
        return ( tmp += value );
    }

    Type& operator -= ( size_t value )
    {
        *( Type* ) this -= value;
        return *this;
    }

    Type operator - ( size_t value ) const
    {
        Type tmp = *this;
        return tmp -= value;
    }

    int operator - ( const Type& right ) const
    {
        return ( m_ptr - right.m_ptr );
    }

    Reference operator [] ( int offset ) const
    {
        return *( *this + offset );
    }

    bool operator == ( const Type& right ) const
    {
        return m_ptr == right.m_ptr;
    }

    bool operator != ( const Type& right ) const
    {
        return m_ptr != right.m_ptr;
    }
};


template<typename T>
class List
{
public:

    typedef List<T> Type;
    typedef typename T* Pointer;
    typedef typename T& Reference;
    typedef typename const T& ConstReference;

    typedef ListIterator<Type> iterator;
    typedef ListIterator<Type> const_iterator;

public:

#define m_elementSize ( sizeof( T ) )

    List()
        : m_data( 0 ),
        m_pointer( 0 ),
        m_ep( 0 ),
        m_length( 0 ),
        m_allocLength( 0 ),
        m_capacity( 0 )
    {
    }

    List( size_t count )
        : m_data( 0 ),
        m_pointer( 0 ),
        m_ep( 0 ),
        m_length( 0 ),
        m_allocLength( 0 ),
        m_capacity( 0 )
        //,m_elementSize( sizeof( T ) )
    {
        reserve( count );
    }

    List( T* a, unsigned int count )
        //: m_elementSize( sizeof( T ) )
    {
        reserve( count );

        ::memcpy( m_data, a, m_capacity );
        m_length = ( int ) count;
    }

    ~List()
    {
        //delete ( ( char* ) m_data );
        if ( m_data )
            ::free( m_data );
    }

    bool reserve( size_t count, bool reset = false )
    {
        if ( initialized() ) return false;

        m_allocLength = count;
        m_capacity = count * m_elementSize;

        char* data = ( char* ) ::malloc( m_capacity ); //new char[ m_capacity ];
        if ( !data )
            throw "Memory cannot be allocated!";

        if ( reset )
            ::memset( data, 0, m_capacity );

        m_data = reinterpret_cast<Pointer>( data );
        m_pointer = m_data;
        m_ep = m_data + count;

        return true;
    }

    void resize( size_t length, bool reset = false )
    {
        if ( length > ( ( ~( ( int ) 0 ) ) >> 2 ) ) throw "BAD LIST RESIZE LENGTH!";

        if ( ( int ) length > m_allocLength )
        {
            int oldCapacity = m_capacity;
            m_capacity = length * m_elementSize;
            m_allocLength = length;

            void* data = ::realloc( m_data, m_capacity );
            if ( reset )
                ::memset( ( ( char* ) data ) + oldCapacity, 0, m_capacity - oldCapacity );

            m_data = reinterpret_cast<Pointer>( data );
            m_pointer = m_data + m_length;
            m_ep = m_data + m_allocLength;
        }
    }

    void push_back( const T& instance )
    {
        if ( !initialized() )
        {
            reserve( 16 );
        }
        if ( m_length + 1 > m_allocLength )
        {
            resize( m_length << 1 );// + 1 );
        }
        ::memcpy( m_pointer, &instance, m_elementSize );
        m_pointer++; //m_pointer = reinterpret_cast<Pointer>( ( char* ) m_pointer + m_elementSize );
        m_length++;
    }

    inline void add( const T& instance )
    {
        push_back( instance );
    }

    void pop_back()
    {
        m_pointer = reinterpret_cast<Pointer>( ( char* ) m_pointer - m_elementSize );
        m_length--;
    }

    Reference back()
    {
        return *reinterpret_cast<Pointer>( ( char* ) m_pointer - m_elementSize );//*( end() - 1 );
    }

    ConstReference back() const
    {
        return *reinterpret_cast<Pointer>( ( char* ) m_pointer - m_elementSize );//*( end() - 1 );
    }

    void deleteAt( int index )
    {
        if ( index < 0 || index >= m_length ) throw "Index outside the bounds of list!";
        Pointer start = m_data + index;

        delete *start;

        removeAt( index );
    }

    void removeAt( int index )
    {
        if ( index < 0 || index >= m_length ) throw "Index outside the bounds of list!";
        Pointer start = m_data + index;

        if ( m_length - index != 1 )
        {
            ::memcpy( start, start + 1, ( m_length - index - 1 ) * m_elementSize );
        }

        m_length--;
        m_pointer = m_data + m_length;
    }

    void move( int srcIndex, int destIndex )
    {
        if ( srcIndex < 0 || srcIndex >= m_length || destIndex < 0 || destIndex >= m_length ) throw "Index outside the bounds of list!";
        if ( srcIndex == destIndex ) return;

        T* tmp = ( T* ) ::malloc( m_elementSize );
        ::memcpy( tmp, m_data + srcIndex, m_elementSize );

        if ( srcIndex < destIndex )
        {
            Pointer start = m_data + srcIndex;
            ::memcpy( start, start + 1, ( destIndex - srcIndex ) * m_elementSize );
        }
        else
        {
            byte_t* p = ( ( byte_t* ) ( m_data + srcIndex + 1 ) ) - 1;
            byte_t* e = p - ( srcIndex - destIndex ) * m_elementSize;
            for ( byte_t* i = p; i > e; i-- )
            {
                ::memcpy( i, i - m_elementSize, 1 );
            }
        }
        ::memcpy( m_data + destIndex, tmp, m_elementSize );
    }

    void shift( int index, int offset )
    {
        move( index, index + offset );
    }

    void swap( int index1, int index2 )
    {
        if ( index1 < 0 || index1 >= m_length || index2 < 0 || index2 >= m_length ) throw "Index outside the bounds of list!";
        if ( index1 == index2 ) return;

        int sIndex = index1, bIndex = index2;

        if ( index1 > index2 )
        {
            sIndex = index2;
            bIndex = index1;
        }

        T* tmp = ( T* ) ::malloc( m_elementSize ); // could be allocated on stack using byte array of sizeof( T ), but with bigger element size it can be problematic

        ::memcpy( tmp, m_data + sIndex, m_elementSize );
        ::memcpy( m_data + sIndex, m_data + bIndex, m_elementSize );
        ::memcpy( m_data + bIndex, tmp, m_elementSize );

        ::free( tmp );
    }

    void clear( bool deallocate = true )
    {
        if ( deallocate )
        {
            // deallocate the buffer
            ::free( m_data );

            m_data = NULL;
            m_allocLength = 0;
            m_capacity = 0;
        }

        m_length = 0;
        m_pointer = m_data;
        m_ep = m_pointer;
    }

    void insert( T& instance, int index )
    {
    }

    void destroy()
    {
        for ( int i = 0; i < m_length; i++ ) delete ( *this )[ i ];
    }

    inline int length() { return m_length; }
    inline int size() { return length(); }
    inline int count() { return length(); }

    bool initialized() { return !!m_data; }

    Pointer toArray()
    {
        T* a = ( T* ) ::malloc( m_allocLength );
        ::memcpy( a, m_data, m_allocLength );

        return a;
    }

    bool contains( T value )
    {
        bool result = false;

        for ( auto i = begin(); i < end(); i++ )
        {
            if ( value == *i )
            {
                result = true;
                break;
            }
        }
        return result;
    }

    int indexOf( T value )
    {
        int result = -1;

        for ( auto i = begin(); i < end(); i++ )
        {
            if ( value == *i )
            {
                result = i - begin();
                break;
            }
        }
        return result;
    }

    Pointer detach()
    {
        Pointer result = m_data;

        m_data = NULL;
        m_allocLength = 0;
        m_capacity = 0;
        m_length = 0;
        m_pointer = m_data;
        m_ep = m_pointer;

        return result;
    }

    T& operator [] ( unsigned int index ) const
    {
        return *( m_data + index );
    }

    T& operator [] ( int index ) const
    {
        return *( m_data + index );
    }

    iterator begin()
    {
        return iterator( this->m_data );
    }

    const_iterator begin() const
    {
        return const_iterator( this->m_data  );
    }

    iterator end()
    {
        return iterator( this->m_pointer);
    }

    const_iterator end() const
    {
        return const_iterator( this->m_pointer );
    }

private:

    Pointer m_data;
    Pointer m_pointer;
    Pointer m_ep; // end pointer
    int m_length;
    int m_allocLength; // full allocated length
    int m_capacity;

#undef m_elementSize
};
